import javax.swing.tree.TreeNode;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class TextBinaryTree {
    static class TreeNode{
        public char val;   //数据域
        public TreeNode left; //左孩子的引用
        public TreeNode right; //右孩子的引用
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree() {
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');
            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            C.left = F;
            C.right = G;
            E.right = H;
            return A;
    }
    // 前序遍历  根   左子树  右子树   递归
    public void preOrder(TreeNode root) {
            if (root == null) {
                return ;
            }
        System.out.print(root.val + " ");
            preOrder(root.left);
            preOrder(root.right);
    }
    public void preOrdernor(TreeNode root) {
        if (root == null) {
            return ;
        }
        TreeNode cur = root;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.println(cur.val + " ");
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }
    //中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    public void inOrdernor(TreeNode root) {
        if (root == null) {
            return ;
        }
        TreeNode cur = root;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.println(top.val + " ");
            cur = top.right;
        }
    }
    //后序遍历
    public void postOrder(TreeNode root) {
        if (root == null) {
            return ;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    public void postOrdernor(TreeNode root) {
        if (root == null) {
            return ;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev ) {
                System.out.print(top.val + " ");
                stack.pop();
                prev = top;
            } else {
                cur = top.right;
            }
        }
    }
    // 获取树中节点的个数
    //子问题思路
     public int size(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = size(root.left);
        int right = size(root.right);
        return left + right + 1;
    }
    int sum = 0;
    //遍历思路
    public int size2(TreeNode root) {
        if (root != null) {
            sum += 1;
        }
        if (root == null) {
            return 0;
        }
        size2(root.left);
        size2(root.right);
        return sum;
    }
    // 获取叶子节点的个数
    //子问题思路
    public int getLeafNodeCount(TreeNode root) {
         if (root == null) {
             return 0;
         }
         if (root.left == null && root.right == null) {
             return 1;
         }
         int leftTree = getLeafNodeCount(root.left);
         int rightTree = getLeafNodeCount(root.right);
         return leftTree + rightTree;
    }
    public int leafNode = 0;
    public int getLeafNodeCount2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            leafNode++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
        return leafNode;
    }
    // 获取第K层节点的个数
    int getKLeavelNodeCount(TreeNode root,int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        int leftLeave = getKLeavelNodeCount(root.left,k-1);
        int rightLeave = getKLeavelNodeCount(root.right,k-1);

        return leftLeave + rightLeave;
    }
    // 获取二叉树的高度
    int getHeight(TreeNode root) {
             if (root == null) {
                 return 0;
             }
             int leftHeight = getHeight(root.left);
             int rightHeight = getHeight(root.right);
             return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1 );
    }
    // 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, int val){
         if (root == null) {
             return null;
         }
         if (root.val == val) {
             return  root;
         }
         TreeNode leftTree = find(root.left,val);
         if (leftTree != null) {
             return leftTree;
         }
         TreeNode rightTree = find(root.right,val);
         if (rightTree != null) {
             return rightTree;
         }
           return null;
    }
    //层序遍历
    public void levelOrder(TreeNode root) {
           if (root == null) {
               return ;
           }
           Deque<TreeNode> queue = new LinkedList<>();
           queue.offer(root);
           while(!queue.isEmpty()) {
                TreeNode cur = queue.poll();
               System.out.print(cur.val + " ");
               if (cur.left != null) {
                   queue.offer(cur.left);
               }
               if (cur.right != null) {
                   queue.offer(cur.right);
               }
           }
        System.out.println();
    }


    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
           if (root == null) {
               return true;
           }
           Deque<TreeNode> queue = new LinkedList<>();
          queue.offer(root);
          while (!queue.isEmpty()) {
              TreeNode cur = queue.poll();
             if (cur != null) {
                 queue.offer(cur.left);
                 queue.offer(cur.right);
             } else {
                 break;
             }
          }
          while (!queue.isEmpty()) {
              TreeNode tmp = queue.poll();
              if (tmp != null) {
                  return false;
              }
          }
          return true;
    }
    //找最近的公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if (leftTree != null && rightTree != null) {
            return root;
        } else if (leftTree != null) {
            return leftTree;
        } else if (rightTree != null) {
            return  rightTree;
        } else {
            return null;
        }
    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        Deque<TreeNode> stack1 = new LinkedList<>();
          getPath(root,p,stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,q,stack2);
        if (stack2.size() > stack1.size()) {
            Deque<TreeNode> tmp = stack2;
            stack2 = stack1;
            stack1 = tmp;
        }
        while (stack1.size()!=stack2.size()) {
            stack1.pop();
        }
        while (!stack1.isEmpty()) {
             if (stack1.peek() == stack2.peek()) {
                 return stack1.peek();
             }
             stack1.pop();
             stack2.pop();
        }
        return null;
    }
    public boolean getPath(TreeNode root, TreeNode node, Deque<TreeNode> stack) {
        if (root == null || node == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean ret1 = getPath(root.left,node,stack);
        if (ret1) {
            return true;
        }
        boolean ret2 = getPath(root.right,node,stack);
        if (ret2) {
            return true;
        }
        stack.pop();
        return false;
    }
}
